package com.atguigu.demo.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class GraphDemo {
    private final ArrayList<String> vertexList; //存储顶点集合
    private final int[][] edges; //存储图对应的邻结矩阵
    private int numOfEdges; //表示边的数目
    //定义给数组boolean[], 记录某个结点是否被访问
    private boolean[] isVisited;
    public static void main(String[] args) {
        int n=5;
        String[] vertexs = {"A", "B", "C", "D", "E"};
        GraphDemo graph=new GraphDemo(n);
        for (String vertex:vertexs) {
            graph.insertVertex(vertex);
        }
        //添加边
        //A-B A-C B-C B-D B-E
		//graph.insertEdge(0, 1, 1); // A-B
		graph.insertEdge(0, 2, 1); //
        graph.insertEdge(0, 3, 1); //
		graph.insertEdge(1, 2, 1); //
		graph.insertEdge(1, 3, 1); //
		graph.insertEdge(1, 4, 1); //
        //显示一把邻结矩阵
        graph.showGraph();
       // graph.dfs();
        graph.bfs();

    }

    //对dfs 进行一个重载, 遍历我们所有的结点，并进行 dfs
    public void dfs() {
        isVisited=new boolean[vertexList.size()];
        for (int i = 0; i <vertexList.size() ; i++) {
            if (!isVisited[i]){
                dfs(isVisited,i);
            }
        }

    }

    private void dfs(boolean[] isVisited, int i) {
        System.out.println(vertexList.get(i));
        //将结点设置为已经访问
        isVisited[i] = true;
        //查找结点i的第一个邻接结点w
        int w = getFirstNeighbor(i);
        while (w!=-1){
          if (!isVisited[w]){
              dfs(isVisited, w);
          }else {
              //如果w结点已经被访问过
              w = getNextNeighbor(i, w);
          }
        }
    }
    //遍历所有的结点，都进行广度优先搜索
    public void bfs() {
        isVisited=new boolean[vertexList.size()];
        for (int i = 0; i < edges.length; i++) {
            if (!isVisited[i]){
                bfs(isVisited,i);
            }
        }
    }

    private void bfs(boolean[] isVisited, int i) {
        LinkedList li=new LinkedList<>();
        li.addLast(i);
        isVisited[i]=true;
        System.out.println(vertexList.get(i));
        while (!li.isEmpty()){
            int u=(Integer) li.removeFirst();
        int m=    getFirstNeighbor(u);
        while (m!=-1){
            if (!isVisited[m]){
                li.addLast(m);
                isVisited[m]=true;
                System.out.println(vertexList.get(m));
            }else {
              m=   getNextNeighbor(u,m);
            }

        }

        }
    }


    private int getNextNeighbor(int i, int w) {
        for (int j = w+1; j < edges.length; j++) {
          if (edges[i][j]>0){
              return j;
          }
        }
        return -1;
    }
    private int getFirstNeighbor(int i) {
        for (int j = 0; j <edges.length; j++) {
            if (edges[i][j]>0){
                return j;
            }
        }
        return -1;
    }

    public GraphDemo(int n){
        edges=new int[n][n];
        numOfEdges=0;
        vertexList=new ArrayList<>();
    }
    //插入结点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }
    //添加边
    /**
     *
     * @param v1 表示点的下标即使第几个顶点  "A"-"B" "A"->0 "B"->1
     * @param v2 第二个顶点对应的下标
     * @param weight 表示
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
    //显示图对应的矩阵
    public void showGraph() {
        System.out.println("  "+vertexList);
        for (int i = 0; i < edges.length; i++) {
            System.out.println(vertexList.get(i)+" "+ Arrays.toString(edges[i]));
        }
//        for (int[]  edgey:edges) {
//            System.out.println(Arrays.toString(edgey));
//        }
    }
}
